/*
 * IDDepthFirstSearch.java
 * 
 * TCSS 435 - Autumn 2012
 * Homework 1
 */

import java.util.*;

/**
 * An iterative deepening depth first search.
 * 
 * @author Dallas Rosson
 * @version Autumn 2012
 */
public class IDDepthFirstSearch {
	
	/**
	 * An iterative deepening depth first search.
	 * 
	 * @param start The starting state.
	 * @param goal The goal to be found.
	 * @return A List representing the path taken to reach the node containing the goal state.
	 */
	public static List<State> solve(State start, State goal) {
						
		// The current depth to be searched.
		int depth = 0;
			
		// The path taken to the goal.
		List<State> path = new LinkedList<State>();
		
		while (depth >= 0) {
					
			System.out.println("Searching at depth: " + depth);
			
			path = DepthFirstSearch.solve(start, goal, depth);
			
			if (path.size() > 0) { // Breaks the loop if the goal is found.
								
				break;
			} else { // Goal not found, go one level deeper.
				
				depth++;
			}
		}		
		
		return path;
	}
}
